package dataMining.VertialTopK2;

/**
 * @author: cuiH
 * Date: 13-7-11
 * 设计存储链表的数据结构
 * 结构图示
 * <p/>
 * \ itemId(存放itemId) \boolean位置 \ sup\next ——》指向下一个节点
 * <p/>
 * 通过top元素引入
 */
public class MyLinkList {
    Boolean isSame ;           //默认情况下是和前一个不相等的，如果相等则直接退出

    /*
    * 设计linkList节点
    * */
    class Node {
        int[] itemId;
        int position;
        int sup;
        Node next;

        Node() {
            itemId = null;
            position = 0;
            sup = 0;
            next = null;
        }
    }

    /*
    * 定义一个尾节点，空的，表示里面没有元素，
    * 这样设计的优势，每次都要去比较最后元素的支持度，这样比较方便
    * */
    Node top = new Node();

    MyLinkList() {
        top.next = null;
    }

    /*
    * 默认的增加方法
    * 增加方法设计：直接将队列设计为顺序递减的队列，这样就直接生成队列
    * 先操作非空，因为空毕竟就一个，所以非空在前，空在后
    * 其中K表示top_K
    * @return 返回添加在boolean表中的位置
    * */
    void add(int[] item, int sup) {

        isSame = false;
        /*
        * 具体实现：1.出next外的node属性赋值
        *           2.根据支持度，找到比该位置小的位置的前一个
        *           3.进行具体的插入操作
        *           4.插入完成后，长度大于最大长度K，则删除,并返回最后一个的position(boolean中进行操作)
        * */
        if (top.next != null) {
            if (this.length() < MyAlgorithm.K) {                              //链表的长度与K的关系，分别进行操作
                //1.基本赋值操作
                Node node = new Node();
                node.itemId = item;
                node.sup = sup;

                /*
                * 2和3.比较插入操作,nextPosition指代插入的位置，nextSup,是指该sup后面的一个支持度  ，
                * 本质为设定next操作
                */
                Node locate = top;
                int nextSup = 0;
                while (locate.next != null) {
                    nextSup = locate.next.sup;
                    if (sup > nextSup) {
                        node.next = locate.next;
                        locate.next = node;
                        break;
                    }
                    locate = locate.next;
                }
                if (nextSup >= sup) {                                  //在最后进行添加的情况
                    locate.next = node;
                }
                //设定position操作
                node.position = this.length();
            } else {
                Node node = new Node();
                node.itemId = item;
                node.sup = sup;

                /*
                * 插入该节点
                * 本质为设定next操作
                */
                Node locate = top;
                int nextSup = 0;
                while (locate.next != null) {
                    nextSup = locate.next.sup;
                    if (sup > nextSup) {
                        node.next = locate.next;
                        locate.next = node;
                        break;
                    }
                    locate = locate.next;
                }

                //大于K时候，获取位置为最后一个位置，并且之前已经添加next，则要进行删除操作
                Node traverse = top;
                while (traverse.next.next != null) {
                    traverse = traverse.next;
                }
                node.position = traverse.next.position;             //获取boolean表中的位置
                traverse.next = null;                                //将之后的一个节点进行删除
            }
        } else {                                                         //当节点为空的时候添加节点的过程
            Node node = new Node();
            node.itemId = item;
            node.position = 1;                                          //进来默认的position为第一个位置
            node.sup = sup;
            top.next = node;
        }
    }

    /*
    * 定义获取链表长度的方法
    * */

    int length() {
        int length = 0;
        Node nodeLen = top;
        if (nodeLen.next == null) {
            return length;
        } else {
            while (nodeLen.next != null) {
                nodeLen = nodeLen.next;
                length++;
            }
            return length;
        }
    }

    /*
    * 需要替换的位置
    * 如果boolean表没有填充满，是未填充的下一个位置
    * 如果填充满了，则是链表的最后一个元素的位置
    * */
    int getReplaceLPosition() {
        int replacePosition = 0;
        Node lastNode = top;
        if (this.length() >= MyAlgorithm.K) {
            while (lastNode.next != null) {
                lastNode = lastNode.next;
            }
            replacePosition = lastNode.position;
        } else {
            replacePosition = this.length();
        }
        return replacePosition;
    }

    int getLastSup() {
        Node last = top;
        if (last.next == null) {
            return 0;
        } else {
            while (last.next != null) {
                last = last.next;
            }
            return last.sup;
        }
    }
}
